package com.brett.frame.learn.sort.choose;

import com.brett.frame.learn.sort.base.BaseSort;
import com.brett.frame.learn.sort.base.Sort;
import com.brett.frame.learn.util.DataBuilder;

/**
 * 堆选择排序
 * @author lenovo
 * {@link https://www.cnblogs.com/jetpie/p/3971382.html}
 *ki ≤ k2i 且 ki ≤ k2i+1（在 n 个记录的范围内，第 i 个关键字的值小于第 2*i 个关键字，同时也小于第 2*i+1 个关键字）
ki ≥ k2i 且 ki ≥ k2i+1（在 n 个记录的范围内，第 i 个关键字的值大于第 2*i 个关键字，同时也大于第 2*i+1 个关键字）
时间复杂度在worst-case是O(nlgn)，average-case是O(nlgn)；空间复杂度在worst-case是O(1)，也就是说heapsort可以in-place实现；heapsort不稳定。
 */
public class HeapChooseSort extends BaseSort implements Sort {

	DataBuilder builer = new DataBuilder();

	@Override
	public int[] sort(int[] arr) {
		// 数组转堆
		this.builderMaxHeap(arr);
		for (int i = arr.length - 1; i > 0; i--) {
			super.exchange(arr, 0, i);
			this.maxHeap(arr, 0, i - 1); // 调整为新堆
		}
		return arr;
	}

	public int[] builderMaxHeap(int[] arr) {
		// 数组转堆
		for (int j = (arr.length - 2) >>1 ; j >= 0; j--) {
			this.maxHeap(arr, j, arr.length - 1);
		}
		return arr;
	}

	protected void maxHeap(int[] arr, int i, int end) {
		int left = 2 * i + 1;
		int right = 2 * i + 2;
		int largest = i;
		if (left <= end && arr[left] > arr[i]) {
			largest = left;
		}
		if (right <= end && arr[right] > arr[largest]) {
			largest = right;
		}
		if (largest != i) {
			super.exchange(arr, largest, i);
			this.maxHeap(arr, largest, end);// 递归
		}
	}

	public int[] getDepth(int len) {
		int layer = (int) Math.ceil(Math.log(len + 1) / Math.log(2));
		int depth = layer - 1;
		System.out.println(String.format("len=%d, layer=%d, depth=%d", len, layer, depth));
		return new int[] { layer, depth };
	}
}
